The data processing capability of systems composed of many processors, each operating on one piece of a problem concurrently, is currently strained even for massively powerful computers. One of the major stumbling blocks to effective utilization of the processors is communication between processors.
A significant limitation of systems that are composed of many individual digital computers is the large amount of communication required. Existing interconnection networks are too costly, too slow, or allow only a small subset of the desired connection patterns. The Layered network of the present invention spans the full range from very cheap, blocking networks to robust, complete routing networks. The system designer may select an appropriate member of the Layered class based on the system's requirements.
Classical interconnection networks (baseline, Banyan, etc.) use distributed routing schemes to avoid the problems associated with centralized network control. The classical networks establish a connection by setting each switch by one of the bits in the "request." The request is merely the number of the processor to which the connection should be made. With an N processor baseline network, each of the log.sub.2 N bits is used to set one of the log.sub.2 N switches of size 2 by 2 in its path. Unfortunately, one complete connection prohibits the existence of many others. Thus, "blocking" occurs when two requests arrive simultaneously at a switch and both need to use the same terminal. Layered networks may choose from more than one digit to route and therefore route connections that would normally be blocked.
The tutorial "Interconnection Networks for Parallel and Distributed Processing", edited by Wu and Feng, published in 1984 by the IEEE Computer Society contains a collection of papers which represented the state-of-the-art in interconnection networks. Among these papers is "A Sampler of Circuit Switching Networks" (Computer, June 1979) that reviews several networks including the Cantor network. This paper gives a simple proof that the Cantor network is non-blocking, (i.e., a path can be found from any unused input to any unused output), but notes that routing algorithms can route at best one path at a time. [See p. 154, Pippenger]
The crossbar switch (see p. 146 of Wu and Feng) can be routed in a fast non-blocking manner, but its cost rises rapidly with the number of processors to be connected. Wu and Feng show in their paper, "The Reverse Exchange Interconnection Network" (IEEE Trans Computer, September 1980), the functional relationship between many of the studied interconnection networks including: Baseline, Omega, Flip, Banyan, and others. They also identify the small subset of all possible permutations that those networks can perform. The topological transformations taught by Wu and Feng may be used in conjunction with the topology of the present invention and within the scope of the invention to provide alternate embodiments.
Unlike the Cantor network, Baseline networks have fast routing algorithms, but they are blocking. Wu and Feng also discuss the Benes network. The Benes network can be constructed by cascading two "baseline type" networks. The Benes network can implement all N factorial (N!) permutations. Furthermore, the routing algorithms that allow all permutations, much less combinations, require centralized matrix manipulation. To summarize, existing networks either are too costly (crossbar), lack an efficient routing algorithm (Cantor, Benes), or fail to implement all permutations and combinations (Baseline).
The crossbar switch (FIG. 1) has been used in many prior interconnection systems for its high speed, repetitive construction, and full interconnect capability. A crossbar is basically a unidirectional device in which the outputs "listen" to the inputs. Each output can listen to any desired input without conflict. The crossbasr's totally non-blocking property and distributed control serves as an ideal standard. However, the crossbar exhibits on the order of O(N.sup.2) cost growth and does not allow special broadcast operations where different listeners receive different values from the same input. (The notation O(N.sup.2) means "on the order of" or, in other words, a value proportional to N.sup.2, where "N" is the number of processing nodes connected to the network.) For example, "Fetch-And-Op" operations are useful in large multiprocessing systems.
These limitations have led investigators to multistage interconnection networks topologically equivalent to Baseline networks, such as the Omega network shown in FIG. 2. The reverse Banyan network of FIG. 3 most closely resembles the Layered network of the present invention from among the classical, Baseline-equivalent networks. Although such networks have distributed routing algorithms, good cost and access delay growth, and support fetch-and-op operations, the blocking property inherent in such networks imposes uncertain delay that is detrimental to the performance of tightly coupled processes. The Cantor network of FIG. 4 is advantageous because of its O(N log.sup.2 N) cost growth and its easily proven non-blocking property. However, setting of the switches for such a network is relatively slow and not adequately distributed.
Five measures of performance of desirable networks are: full interconnection, distributed routing algorithm, minimal access time, low cost growth, and support for special broadcast operations (such as fetch-and-op). The new class of Layered interconnection networks of the present invention satisfies these criteria and can provide all N.sup.N interconnection patterns with O(N log.sup.3 N) cost growth.
A new class of multistage interconnection networks, dubbed "Layered" Networks, for exchange of data between processors in a concurrent computer system are introduced by the present invention. Layered Networks provide an alternative to highly-blocking classical networks equivalent to the Baseline network. Layered Networks support a much richer set of connnections than classical networks. A subclass of Layered Networks, "binary, fully-Layered" networks, is shown to implement all connections possible with a crossbar using the distributed switch setting algorithm, but with much slower cost growth when scaled up to systems with more processors.